package LeetCode;



import java.util.HashMap;
import java.util.List;

public class No142 {
    public ListNode detectCycle(ListNode head) {

        /*
        当快慢指针第一次相遇的时候设置一个慢指针从头跑，快指针咱不管他，之前的慢指针继续走。当第二个慢指针走到之前慢指针和快指针
        相遇的地方的时候，你会发现那个没停的慢指针是不是应该走了快指针的距离，那是不是两个慢指针应该在之前快慢指针相遇的地方又相
        遇了。如果想让两个速度一样的指针在环里相遇，那只有在他们入环的时候相遇才能在一起。所以由此可以推论出两个慢指针第一次相遇
        的时候就是入环的节点。
         */
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            if (fast.next == null) return null;
            else fast = fast.next.next;
            if (fast == slow) break;
            slow = slow.next;
        }
        ListNode pre = head;
        while (pre != slow) {
            pre = pre.next;
            slow = slow.next;
        }
        return slow;


//        HashMap<ListNode,Integer> map = new HashMap<>();
//        int n = 0;
//        while(head!=null){
//            if(map.containsKey(head)) return head;
//            map.put(head,n++);
//            head=head.next;
//        }
//        return null;
    }
}
